/**
 * @file main.cpp
 * @author 张奕欣 3190105655 (3190105655@zju.edu.cn)
 * @brief 
 * @version 0.1
 * @date 2022-10-16
 * 
 * @copyright Copyright (c) 2022
 * 
 */
#define _CRTDBG_MAP_ALLOC
#include <stdlib.h>
#include <crtdbg.h>
#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>
#include <chrono>
#include <iomanip>
#include "BinarySearchTree.h"
using namespace std;

//template <typename Comparable>
//void BSTSorting(std::vector<Comparable>& _arr, int _mode=0);
//此处void BSTSorting 不需要声明。定义也可视为声明的一种，叫包含了显式初始化的声明。
/**
     * @brief 将数组arr排序
     * 当 _mode = 0 时, 不乱序；
     * 当 _mode = 1时, 先对数组 _arr 乱序后再排序;
     * @param _mode 
    */ 
template <typename Comparable>
void BSTSorting( std::vector<Comparable>& _arr, int _mode=0 )
{
    if (_mode != 0 && _mode != 1 )
    {
        cout << "There are some problems in mode." << endl;
        return;
        // return 和exit(-1)的区别：exit(-1)结束整个运行，retrun只是结束这个函数
        // 在void()函数中不能retrun 一个常数。
    }

    if ( _arr.size() == 0 )
    {
        cout << "Empty Vector." << endl;
        return;
    }
    //如果_mode = 1时先乱序
    if ( _mode == 1)
        {
            random_shuffle(_arr.begin(),_arr.end());
        }

    //将数组放入二叉树中
    BinarySearchTree<Comparable> t; //在定义函数中声明变量的方法
    for (auto i = _arr.begin();
        i != _arr.end();
        i++)
    {
        t.insert(*i);
    }
    if (_arr.size()<10)
    {
        t.printTree();
        cout << endl;
    }
}

void shuzu(int *a,int n)//生成范围在l~n的顺序数组 
{
	for(int i=0;i<n;i++){
		a[i]=i;//插入
	}
}

    // Test program
int main( )
{
    BinarySearchTree<int> t;
    int NUMS = 20;
    const int GAP  =   3711;
    int i;

    cout << "Checking... (no more output means success)" << endl;
    t.insert(1);
    cout << "test makeEmpty()" << endl;
    t.printTree();
    cout << endl;
    t.makeEmpty();
    cout << "print tree: ";
    t.printTree();

    //测试insert
    for( i = GAP; i != 0; i = ( i + GAP ) % NUMS )
        t.insert( i );
    cout << "output tree: " << endl;
    t.printTree();
    cout << endl;

    //测试remove
    for( i = 1; i < NUMS; i+= 2 )
        t.remove( i );
    cout << "Output t after removing odd number: " << endl;
    t.printTree();
    cout << endl;

    //测试 contains
    cout << "test contains" << endl;
    t.contains(2);
    t.contains(1);

    //测试findmax 和 findmin
    cout << "test findMax() and findMin()" << endl;
    t.findMax();
    t.findMin();

    BinarySearchTree<int> t1(std::move(t));
    /// 移动构造函数, 结束之后, t 的实质内容转移给 t4. t 已经没有实质
    /// 内容. 这里 move 的作用是把一个左值变成一个右值.
    cout << "Mobile structure: ";
    t1.printTree();
    cout << endl;

    //移动赋值
    t = std::move(t1);
    cout << "Mobile assignment: " ;
    t.printTree();
    cout << endl;

    BinarySearchTree<int> t2(t);
    /// 复制构造函数的测试．结束之后, t2 是一个新的类实体.
    cout << "structure copied: ";
    t2.printTree();
    cout << endl;

    //复制赋值
    t = t2;
    cout << "Copid assignment: " ;
    t.printTree();
    cout << endl;

    //测试数组 _arr 排序
    BinarySearchTree<int> t3;
    cout << "Test sort: " << endl;

    vector<int> input1;
    input1 = {3, 0, 7, 2, 5, 9, 4};
    cout << "Before:\t";
    for (vector<int>::iterator it = input1.begin();
	    it != input1.end();
	    it++)
    {
    cout << *it << '\t';
    }
    cout << endl;
    cout << "After:\t";
    BSTSorting(input1, 1);
    BSTSorting(input1, 2);

    //测试_mode=0的最坏效率
    vector<double> TimeWorst;
    vector<double> TimeAve;

    cout << "Test the worst efficiency when _mode=0" <<endl;
    for (int size = 30;size <= 30000;size *=10)
    {
        int a[size];
        shuzu(a,size); //生成数组
        vector<int> v(a,a+size); //将生成的数组复制给v
        clock_t startTimeWorst = clock();
        BSTSorting(v,0);
        clock_t endTimeWorst = clock();
        TimeWorst.push_back(double(endTimeWorst - startTimeWorst) / CLOCKS_PER_SEC);
	    //system("pause");按任意键继续
    }
    cout << "Time Worst:" <<endl;
	for (int i=0;i<TimeWorst.size();i++)
        cout<<TimeWorst.at(i)<< "s" << endl;

    //测试_mode=1的平均效率
    cout << "Test the average efficiency when _mode=1" <<endl;
    for (int size = 30; size <= 300000; size *= 10)
    {
        int a[size];
        shuzu(a,size); //生成数组
        vector<int> v(a,a+size); //将生成的数组复制给v
        vector<float> time;
        for (int i = 0; i < 50; i++)
        {
            clock_t startTimeAve = clock();
            BSTSorting(v,1);
            clock_t endTimeAve = clock();
            time.push_back(double(endTimeAve - startTimeAve) / CLOCKS_PER_SEC);
        }
        float mean;
        float sum;
        sum = 0.0;
        for (int i =0; 
            i < 50; 
            i++ )
        {
            sum += time[i];
        }
        TimeAve.push_back(sum/50);
    }
    
    cout << "Time Average:" <<endl;
	for (int i=0;i<TimeAve.size();i++)
        cout<<TimeAve.at(i)<< "s" <<endl;

    //检查内存是否泄露
    _CrtDumpMemoryLeaks();
    cout << "Finished testing" << endl;

    return 0;
}